# -*- coding=utf-8-*-
"""
@File:memory_selection
@Author:Created by Han X.Y
@Date:on 2021/7/9 8:37 
"""
"""
假设按照升序排序的数组在预先未知的某一个点进行了旋转。
(例如：数组[0,1,2,4,5,6,7]可能变成[4,5,6,0,1,2])
搜索一个给定的目标值。如果数组中存在这个目标值在返回它的索引。
否则返回-1。你可以假定数组中不存在重复的元素。

你的算法时间复杂度必须是O(logn)级别

"""


def search33(nums, target):
    """
    寻找旋转点，如果存在则返回它的索引，否则返回-1
    """
    if len(nums) == 0:
        return -1
    left, right = 0, len(nums)-1
    while left <right:
        mid = right >> 1
        print('mid:',mid,'right:',right)
        if nums[mid] == target:
            return mid
        elif nums[mid] > nums[left]:
            if nums[left] <= target and target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            if nums[left] == nums[mid]:
                left += 1
            else:
                right += 1
        print(f"num[left]={nums[left]},nums[right]={nums[right]},nums[mid]={nums[mid]},target={target}")
    return -1

if __name__=='__main__':
    a=[4,5,6,7,0,1,2]
    print(search33(a,0))